from typing import List

class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.count = N  # 连通块个数，每当有连通块合并即可减少一个连通块
    
    def find(self, N):
        while N!=self.parent[N]:
            self.parent[N] = self.parent[self.parent[N]] # 路径压缩 只压缩一级
            N = self.parent[N]
        return N
    
    def find_recursion(self, N):
        if N == self.parent[N]:
            return N
        else:
            pN = self.find_recursion(self.parent[N]) 
            self.parent[N] = pN 
            # 全路径压缩 每个节点直接指向最终的父节点
            # 利用了函数调用栈来保存路径上的节点
            # 不想用函数调用栈保存就自己开个stack保存节点
            return pN
	
	def find_recursion2(self, N):
		# 代码简洁版本
		if self.parent[N] != N:
			self.parent[N] = self.find_recursion2(self.parent[n])
		return self.parent[N]
    
    def union(self, A, B):
        pA = self.find(A)
        pB = self.find(B)
        print('A:{} pA:{} B:{} pB:{}'.format(A, pA, B, pB))
        if pA == pB:
            return
        else:
            self.parent[pB] = pA # 错写成self.parent[B] = A了 debug一个小时
            self.count -= 1

class UnionFind2:
	# 代码简洁版本
	def __init__(self, n):
        self.parent = list(range(n))

    def union(self, index1: int, index2: int):
        self.parent[self.find(index2)] = self.find(index1)

    def find(self, index: int) -> int:
        if self.parent[index] != index:
            self.parent[index] = self.find(self.parent[index])
        return self.parent[index]
        
            
# leetcode 765
class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        """
        贪心就是一个个满足情侣的要求，复杂度在N^2
        可以用并查集加速，用额外的空间 换取时间
        """
        N = len(row) // 2 # N对情侣
        U = UnionFind(N) # 情侣的编号可以由 自己编号//2 获得
        for i in range(0, len(row), 2):
            U.union(row[i]//2, row[i+1]//2)
        
        print('N:{} count:{}'.format(N, U.count))
        return N - U.count

row = [5,6,4,0,2,1,9,3,8,7,11,10]

res = Solution().minSwapsCouples(row)
print(res)